МІНІСТЕРСТВО ОСВІТИ І НАУКИ МОЛОДІ ТА СПОРТУ УКРАЇНИ
Технічний Коледж
Національного університету «Львівська політехніка»
Відділення Інформаційних Технологій
та Комп’ютерної Техніки
Лабораторна робота №5
З дисциплiни «Алгоритми та структури даних»
Львів 2012
План
1.Тема
2.Мета
3.Основні теоретичні відомості
4.Розробка структурних даних
5.Розробка алгоритму
6.Текст робочої програми
7.Тестування
8.Висновок
1.Тема
Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ).
2.Мета
Ознайомлення зі способом подання алгоритму на прикладі машини Тьюрінга.
Завдання:
Виконати операцію додавання двох двійкових чисел:
Z=(X+Y)
Результат розташувати на місці вхідних даних, де
X – день народження (дата)
Y – номер варіанту
Побудувати модель одно стрічкової детермінованої Машини Тьюринга, яка б виконувала ряд команд
{A}x{Q}->{A}{L,R,S}{Q}, де
L – зсув головки вліво
R – зсув головки вправо
S – Головка залишається на місці.
Й мала б вигляд:
M=<A,Q,q0,qr,a0,p>, де
A – кінцева множина символів зовнішнього алфавіту,
Q – кінцева множина символів внутрішнього алфавіту,
q1 – початковий стан,
q0 – кінцевий стан,
q0, q1 Є Q,
a0 – позначення нульової комірки стрічки.
Зобразити роботу машини Тьюрінга до початку виконання програми та після всіх пройдених команд. Початковим станом МТ вважати крайнє праве положення головки на стрічці.
3.Основні теоретичні відомості
Основним призначенням математичних ФАС є дослідження проблем розв’язності. Для цієї проблеми вимога елементарності кроку є необхідною. Оскільки ця вимога не може бути математично точно сформульована, вона інтерпретується як умова загальної зрозумілості. Математичні моделі ФАС ( вийнятки становлять рекурсивні функції) використовують елементарні операції типу розпізнавання символу, трасування, заміна або зміщення. Всі ці операції нагадують дитячу гру з кубиками, тому можуть вважатись загальнозрозумілими або елементарними.
Прикладом ФАС є машина Тьюрінга.
Маши́на Тю́ринга — математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюринга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюринга ввів американський математик Еміль Пост.
Основна ідея, що лежить в основі машини Тюринга, дуже проста. Машина Тюринга — це абстрактна машина (автомат), що працює зі стрічкою, що складається із окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок і яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ із комірки, на яку вказує голівка та, на основі зчитаного символу та внутрішнього стану, робиться наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку або пересунути голівку на одну комірку ліворуч або праворуч.
4.Розробка структурних даних
Змінна
Опис
Тип
Dn
День народження
Int
Nv
Номер варіанту
int
Sum
Сума
Int
Dnd
Д.Н. в двійковому форматі
Int [3]
Nvd
Н.В. в двійковому форматі
Int [5]
Sumd
Сума в двійковому форматі
Int [5]
Таблиця внутрішніх станів
Q\A
0
1
+
_
Q₁
Q₂1L
Q11L
Q₂
Q₂0L
Q₂1L
Q3_L
Q₃
Q3_L
Q3_L
Q0__S
5.Розробка алгоритму
Блок схема
Граф схема
Словесний алгоритм
Підключення бібліотек
Оголошення змінних
Введення даних
Додавання десяткових змінних
Переведення змінних в двійковий масив
Переведення суми в двійковий масив
Виведення результату
Завершення програми
6.Текст робочої програми
#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std;
int main ()
{
int dn,nv,sum;
static int dnd[3],nvd[5],sumd[5];
int i;
cout<<"Vvedit datu narodzhennia, nomer variantu"<<endl;
cin>>dn>>nv;
sum=dn+nv;
for (int i=0;i<3;i++)
{
dnd[3-i-1]=dn%2;
dn=dn/2;
}
for (int i=0;i<5;i++)
{
nvd[5-i-1]=nv%2;
nv=nv/2;
}
for (int i=0;i<5;i++)
{
sumd[5-i-1]=sum%2;
sum=sum/2;
}
cout<<"\ndatu narodzhe...
